package com.nowcoder.Offer.Array;

import org.junit.Test;

/**
 * 排序矩阵中第k小的数
 */
public class KthSmallestInSortMatrix {

    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length - 1;
        int l = matrix[0][0], r = matrix[n][n];
        while(l < r){
            int mid = (l+r) >>> 1;
            int count = countNotMoreThanMid(matrix, mid, n);
            if(count < k){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
    }


    public int countNotMoreThanMid(int[][] matrix, int mid, int n){
        int count = 0;
        int j = 0, i = n;//从左下角开始统计
        while(j <= n && i >= 0){
            if(matrix[i][j] <= mid){
                count += i + 1;
                j++;
            }else{
                i--;
            }
        }
        return count;
    }

    @Test
    public void test(){
        int[][] matrix = {
                {1,5,9},
                {10,11,13},
                {12,13,15}
        };
        System.out.println(kthSmallest(matrix,8));
    }
}
